package leetcode_500;

import java.util.HashSet;
import java.util.Set;

/**
 *@author 周杨
 *UniqueSubstringsInWraparoundString_467 计算一个环形26位字符串的子串个数
 *describe:用备忘录记录最后一位的出现最长长度  AC 50%
 *2018年8月28日 下午4:26:59
 */
public class UniqueSubstringsInWraparoundString_467_ {
	
	public static void main(String[] args) {
		UniqueSubstringsInWraparoundString_467_ test=new UniqueSubstringsInWraparoundString_467_();
		System.out.println(test.findSubstringInWraproundString1("zabyzab"));
	}
	
	/**
	 * describe:每次记录最后一位的出现最长长度 
	 * 2018年8月28日 下午4:23:34
	 */
	public int findSubstringInWraproundString1(String p) {
		if(p.length()==0)
			return 0;
        int dp[]=new int[26];//dp里装的是以该字符结尾的最长长度的字符串备忘录
        int temp=p.charAt(0)-'a',res=0,count=1;//temp放上一个字符
        for(int i=1;i<p.length();++i) {
        	int now=p.charAt(i)-'a';
            if(dp[temp]<count) {
        		res+=count-dp[temp];//一定要减去原始差值
        		dp[temp]=count;//子串也要加入备忘录
        	}
        	if((temp+1)%26==now) {//连在一起了
        		++count;
        	}
        	else {
        		count=1;//reset count
        	}
    		temp=now;
        }
        //组织结尾字符串;
        if(dp[temp]<count) {
        	res+=count-dp[temp];
        }
        return res;
    }
	

}
